Virtual worlds provide graphically rendered simulated environments in which multiple individuals may jointly participate in a shared experience. For example, virtual worlds have been used to simulate fictional gaming environments, real world locations and surroundings and real life activities and interactions. Typically, users may operate a client application or module on their own computer or other device while interfacing with a virtual world server that coordinates and manages data corresponding to multiple clients.
One aspect of creating and managing a virtual world is the tracking and identification of user positions within the environment. In particular, the position of one character or user (represented by an avatar) generally needs to be broadcast to other characters or users so that the other characters or users' clients can graphically depict avatars based on location, and allow communication between appropriately located avatars. This allows a user to see other users within a viewable proximity in the virtual world and also allows the client application to determine when to render other avatars on the user's display. In some instances, a virtual world may include hundreds of thousands (or more) simultaneous users. Accordingly, the amount of bandwidth required to transmit the positions of each avatar may be substantial.
One known method for determining which avatar positions to transmit to a given client is described in U.S. Pat. No. 7,181,690 (“Leahy '690”) and U.S. Pat. No. 7,493,558 (“Leahy '558’), both to Leahy et al. In both Leahy '690 and Leahy '558, the server is configured to determine a list of N avatars, and their positions, nearest to the location of the user, and transmit such information to the user's client software. In Leahy, the list of N avatars nearest to the location of the user may represent less than all of the users occupying the virtual world. Such a solution is not preferred, however, because a user knows nothing about distant users at all, which makes it difficult for the user to located distantly-located friends, find a quiet area in the virtual world to perform some action in relative isolation, or locate a crowded area in the virtual world to interact with many other users.